/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let m = grid.length // 获得网格的行数
  if (m === 0) return 0 // 如果行数是0 直接返回0
  let n = grid[0].length // 获得列数
  const dummy = -1 // 用来和后面的合并
  const dirs = [[1, 0], [0, 1]] // 方向数组
  const uf = new UnionFind(m * n) // 生成m*n的元素大小的并查集
  for (let x = 0; x < m; x++) {
    for (let y = 0; y < n; y++) {
      if (grid[x][y] === '0') {
        // 如果网格是0 就和dummy合并
        uf.union(n * x + y, dummy)
      } else if (grid[x][y] === '1') {
        // 如果这个是1 那么就向右向下尝试
        for (let d of dirs) {
          let r = x + d[0]
          let c = y + d[1]
          if (r >= m || c >= n) continue // 越界下一次
          if (grid[r][c] === '1') {
            // 如果这个是1 那就和当前的饿网格进行合并
            uf.union(n * x + y, n * r + c)
          }
        }
      }
    }
  }
  return uf.getCount()
};
class UnionFind {
  constructor(n) { //构造一个大小为n的集合
    this.count = n // 子集的个数
    this.parent = new Array(n) // 每个元素对应的父节点
    this.size = new Array(n)  // size数组记录着每棵树的大小
    for (let i = 0; i < n; i++) {
      this.parent[i] = i; // 自己是自己的parent 父节点指向本省
      this.size[i] = 1; // 子集个数都是1
    }
  }

  union (p, q) { //连通结点p和结点q, p和q都是索引
    let rootP = this.find(p);
    let rootQ = this.find(q); // 找到各自的根节点
    if (rootP === rootQ) return // 如果相同 就不需要合并
    // 元素数量小的接到数量多的下面，这样比较平衡
    if (this.size[rootP] > this.size[rootQ]) { // 比较这两个根节点的子集的元素个数
      // 让元素个数小的连接到元素个数大的后面
      this.parent[rootQ] = rootP; // 让q的父节点等于p
      this.size[rootP] += this.size[rootQ]; // p的元素的个数就是原来子集的+q的
    } else {
      this.parent[rootP] = rootQ; // 否则让p的父节点等于q
      this.size[rootQ] += this.size[rootP]; // q的元素个数等于原来的加上p的
    }
    this.count--; // 子集的数量要--
  }

  isConnected (p, q) { //判断p,q是否连通
    return this.find(p) === this.find(q) // p,q的根相同 就在一个子集
  }

  find (x) { //找到x结点的root
    while (this.parent[x] != x) { // 如果这个元素的parent是自己就退出循环
      // 进行路径压缩
      this.parent[x] = this.parent[this.parent[x]]; // 让当前的父节点 指向这个父节点的父节点
      x = this.parent[x]; // 让当前的等于当前的父节点
    }
    return x; // 找到根节点
  }

  getCount () { //返回子集个数
    return this.count
  }
}
numIslands([
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "0"]
])
